package TrueTopic;

import java.util.ArrayList;
import java.util.List;

public class LuJingShu {
    // 定义一个图
    static int[][] Graph = {
            {0,1,1,0},
            {0,0,0,0},
            {0,1,0,1},
            {0,1,0,0}
    };
    // 顶点个数
    static int G_length = 4;
    // visit数组，用于在dfs中记录访问过的顶点信息。
    static int[] visit = new int[G_length];
    //存储每条可能的路径
    static ArrayList<Character> path = new ArrayList<>();
    // 用于存储所有路径的集合
    static ArrayList<String> ans = new ArrayList<>();
    //起点和终点
    static int start;
    static int end;


    static void dfs(int u){
        visit[u] = 1;
        path.add((char)((int)'A'+u));
        if(u == end){
            ans.add(path.toString());
        }else{
            for (int i = 0; i < G_length; i++) {
                if(visit[i]==0&&i!=u&&Graph[u][i]==1){
                    dfs(i);
                }
            }
        }
        path.remove(path.size()-1);
        visit[u] = 0;
    }

    public static void main(String[] args) {
        start = 0;
        end = 1;
        dfs(start);
        System.out.println(ans);
    }
}
